package _0_2_背包问题

/*
卡码网题意链接:
https://kamacoder.com/problempage.php?pid=1046

代码随想录 动态规划章节
0-1背包问题  二维数组解法

题意:
	有 n 件物品, 和一个最多能背重量为 w 的背包.
	第 i 件物品的重量为weight[i], 得到的价值是value[i].
	每件物品只能用一次.

	求解将哪些物品装入背包, 总价值最大?

例如物品和背包信息如下:
物品列表:
		重量		价值
物品0	1		15
物品1	3		20
物品2	4		30

当前背包最大容量为4

思路: 动态规划
一. dp[i][j]数组含义
	dp[i][j]: 从下标为第[0-i]个的物品范围中, 任意取搭配方案, 放进容量为j的背包, 所能装的总价值

二. 递推公式:
	dp[i][j]有两个方向可以推出值是多少:
	* 不放物品i:
		dp[i-1][j]
	* 放物品i:
		dp[i-1][j-weight[i]] + weight[i]
不放当前物品:i-1  让出当前物品空间:j-weight[i]   weight[i]:加上当前物品的重量

三. dp数组如何初始化
横坐标: 第i个物品
纵坐标: 装j重量的背包

		0		1		2		3		4      重量
物品0	0		15		15		15		15

物品1	0

物品2	0

1.装0重量背包时, 能装满的最大价值肯定为0, 什么都不能放, 所以第0列直接初始化为0
2.第0列初始化:
	由递推公式看出, dp[i][j]都是根据dp[i-1]上一行得出的, 那么i为0时的最上面一行就需要进行初始化
  第0行初始化:
	最上面一行表示, 使用物品0, 装各个重量的目标值
  	物品0的重量为1, 恰好每个目标重量都能装, 所以填充上物品0的价值15
  其它位置初始化:
	由递推公式:
		dp[i][j] { dp[i-1][j]
				 { dp[i-1][j-weight[i]] + weight[i]  可得,
		当前dp[i][j]肯定是从当前位置的左上方推得的, 所以初始化多少的无所谓, 都会被覆盖  初始化为0即可

四. 确定遍历顺序
	先遍历物品, 还是先遍历背包呢?  都可以!
	因为dp[i-1][j],
       dp[i-1][j-weight[i]] + weight[i] 两种情况都是在dp[i][j]的左上角递推过来的, 都能满足推导需要

*/

func test_2_wei_bag_problem1(weight, value []int, bagweight int) int {
	//1.定义dp数组
	dp := make([][]int, len(weight))
	for i, _ := range dp {
		dp[i] = make([]int, bagweight+1)
	}
	//2.初始化
	for j := bagweight; j >= weight[0]; j-- {
		dp[0][j] = dp[0][j-weight[0]] + value[0]
	}
	//3.递推公式
	for i := 1; i < len(weight); i++ { //先遍历物品, 第0行已经被初始化了, 从第1行开始
		//正序,也可以倒序
		for j := 0; j <= bagweight; j++ { //背包重量, 从0填充到背包的最大容量
			if j < weight[i] { //如果当前背包容量j 比当前物品的重量还小, 说明肯定不能放, 选择不放的方案, dp[i][j]=dp[i-1][j]
				dp[i][j] = dp[i-1][j]
			} else { //否则就是可以放, 那么就考虑 dp[i-1][j] 和 dp[i-1][j-weight[i]] + weight[i] 两者的较大者
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
			}
		}
	}

	//4.返回最右下角的值, 即: 背包容量为题目值, 且考虑了所有物品
	return dp[len(weight)-1][bagweight]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	weight := []int{1, 3, 4}
	value := []int{15, 20, 30}
	test_2_wei_bag_problem1(weight, value, 4)
}
